package com.leetcode.algorithm.y19.m03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * 
 * (done)257. 二叉树的所有路径
 * (done)112. 路径总和
 * (done)113. 路径总和 II
 * (done)437. 路径总和 III
 * (done)993. 二叉树的堂兄弟节点
 * @author: jie.deng
 * @time: 2019年3月9日 下午11:07:30
 */
public class MySolution0309 {
    /**
     * 257. 二叉树的所有路径
     * 
     * 给定一个二叉树，返回所有从根节点到叶子节点的路径。
     * 
     * 说明: 叶子节点是指没有子节点的节点。
     * 
     * 示例:
     * 
     * 输入:
     * 
     *    1
     *  /   \
     * 2     3
     *  \
     *   5
     * 
     * 输出: ["1->2->5", "1->3"]
     * 
     * 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
     * @param root
     * @return
     */
	public List<String> binaryTreePaths(TreeNode root) {
		List<String> list = new ArrayList<String>();
		if (root == null) {
			return list;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		StringBuilder path = new StringBuilder();
		Map<TreeNode, String> rightNodePathPrefixMap = new HashMap<TreeNode, String>();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			if (rightNodePathPrefixMap.containsKey(node)) {
				path = new StringBuilder(rightNodePathPrefixMap.get(node));
			}
			if (path.length() > 0) {
				path.append("->");
			}
			path.append("" + node.val);
			if (node.right != null) { // 右子树先入栈，左子树后入栈，这样出栈就是先左节点后右节点
				stack.push(node.right);
				rightNodePathPrefixMap.put(node.right, path.toString());
			}
			if (node.left != null) {
				stack.push(node.left);
			}
			if (node.left == null && node.right == null) { // 叶子结点
				list.add(path.toString());
			}
		}
		return list;
	}
    
	
	/**
	 * 112. 路径总和
	 * 
   * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
   * 
   * 说明: 叶子节点是指没有子节点的节点。
   * 
   * 示例: 
   * 给定如下二叉树，以及目标和 sum = 22，
   * 
   *               5
   *              / \
   *             4   8
   *            /   / \
   *           11  13  4
   *          /  \      \
   *         7    2      1
   * 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
	 * @param root
	 * @param sum
	 * @return
	 */
	public boolean hasPathSum(TreeNode root, int sum) {
		if (root == null) {
			return false;
		}
		if (root.left == null && root.right == null) {
			return root.val == sum; // 叶子节点
		}
		if (root.left != null && root.right != null) {
			return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
		}
		TreeNode child = root.left == null ? root.right : root.left;
		return hasPathSum(child, sum - root.val);
	}
	
	/**
	 * 113. 路径总和 II
	 * 
	 * 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
	 * 
	 * 说明: 叶子节点是指没有子节点的节点。
	 *	 
	 * 示例:
	 * 给定如下二叉树，以及目标和 sum = 22，
	 * 
	 *               5
	 *              / \
	 *             4   8
	 *            /   / \
	 *           11  13  4
	 *          /  \    / \
	 *         7    2  5   1
	 * 返回:
	 * 
	 * [
	 *    [5,4,11,2],
	 *    [5,8,4,5]
	 * ]	 
	 * @param root
	 * @param sum
	 * @return
	 */
	public List<List<Integer>> pathSumII(TreeNode root, int sum) {
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		if (root == null) {
			return list;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		List<Integer> pathList = new ArrayList<Integer>();
		int pathSum = 0;
		Map<TreeNode, List<Integer>> rightNodePathPrefixMap = new HashMap<TreeNode, List<Integer>>();
		Map<TreeNode, Integer> rightNodePathPrefixSumMap = new HashMap<TreeNode, Integer>();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			if (rightNodePathPrefixMap.containsKey(node)) {
				pathList = rightNodePathPrefixMap.get(node);
				pathSum = rightNodePathPrefixSumMap.get(node);
			}
			pathList.add(node.val);
			pathSum += node.val;
			if (node.right != null) { // 右子树先入栈，左子树后入栈，这样出栈就是先左节点后右节点
				stack.push(node.right);
				rightNodePathPrefixMap.put(node.right, new ArrayList<Integer>(pathList));
				rightNodePathPrefixSumMap.put(node.right, pathSum);
			}
			if (node.left != null) {
				stack.push(node.left);
			}
			if (node.left == null && node.right == null) { // 叶子结点
				if (pathSum == sum) {
					list.add(pathList);
				}
			}
		}
		return list;
	}
	
    /**
     * 437. 路径总和 III
     * 
     * 给定一个二叉树，它的每个结点都存放着一个整数值。
     * 
     * 找出路径和等于给定数值的路径总数。
     * 
     * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
     * 
     * 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
     * 
     * 示例：
     * 
     * root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
     * 
     *       10
     *      /  \
     *     5   -3
     *    / \    \
     *   3   2   11
     *  / \   \
     * 3  -2   1
     * 
     * 返回 3。和等于 8 的路径有:
     * 
     * 1.  5 -> 3
     * 2.  5 -> 2 -> 1
     * 3.  -3 -> 11
     * @param root
     * @param sum
     * @return
     */
	public int pathSumIII(TreeNode root, int sum) {
		if (root == null) {
			return 0;
		}
		Map<TreeNode, List<Integer>> map = new HashMap<TreeNode, List<Integer>>();
		map.put(root, Arrays.asList(root.val));
		buildSumMap(root, 0, map);

		int pathCount = 0;
		Collection<List<Integer>> values = map.values();
		for (List<Integer> list : values) {
			for (Integer pathSum : list) {
				if (pathSum == sum) {
					pathCount++;
				}
			}
		}
		return pathCount;
	}
    
	private void buildSumMap(TreeNode t, int level, Map<TreeNode, List<Integer>> map) {
		if (t.left != null) {
			List<Integer> list = new ArrayList<Integer>();
			list.add(t.left.val);
			List<Integer> parentSum = map.get(t);
			for (Integer sum : parentSum) {
				list.add(sum + t.left.val);
			}
			map.put(t.left, list);
			buildSumMap(t.left, level + 1, map);
		}
		if (t.right != null) {
			List<Integer> list = new ArrayList<Integer>();
			list.add(t.right.val);
			List<Integer> parentSum = map.get(t);
			for (Integer sum : parentSum) {
				list.add(sum + t.right.val);
			}
			map.put(t.right, list);
			buildSumMap(t.right, level + 1, map);
		}
	}

    /**
     * 993. 二叉树的堂兄弟节点
     * 
     * 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
     * 
     * 如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。
     * 
     * 我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。
     * 
     * 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 
     * 输入：root = [1,2,3,4], x = 4, y = 3
     * 输出：false
     * 示例 2：
     * 
     * 
     * 输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
     * 输出：true
     * 示例 3：
     * 
     * 
     * 
     * 输入：root = [1,2,3,null,4], x = 2, y = 3
     * 输出：false
     *  
     * 
     * 提示：
     * 
     * 二叉树的节点数介于 2 到 100 之间。
     * 每个节点的值都是唯一的、范围为 1 到 100 的整数。
     * @param root
     * @param x
     * @param y
     * @return
     */
	public boolean isCousins(TreeNode root, int x, int y) {
		if (root == null || (root.val == x || root.val == y)) {
			return false;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		return isCousins(queue, 1, x, y);
	}

	private boolean isCousins(Queue<TreeNode> queue, int limit, int x, int y) {
		int limitNew = 0;
		boolean findOneCousins = false;
		while (limit > 0) {
			boolean findOneBrother = false;
			TreeNode t = queue.poll();
			TreeNode curr = t.left;
			if (curr != null) {
				queue.offer(curr);
				limitNew++;
				if (curr.val == x || curr.val == y) {
					if (findOneCousins) {
						return true;
					}
					findOneCousins = true;
					findOneBrother = true;
				}
			}
			curr = t.right;
			if (curr != null) {
				queue.offer(curr);
				limitNew++;
				if (curr.val == x || curr.val == y) {
					if (findOneBrother) {
						return false; // x、y是兄弟节点
					}
					if (findOneCousins) {
						return true; // x、y是堂兄弟节点
					}
					findOneCousins = true;
				}
			}
			limit--;
		}
		return !findOneCousins && isCousins(queue, limitNew, x, y);
	}
}
